package java学习.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 刘世锦
 * 2022-10-09 13:56:32	 当前时间
 */
//给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足： 
//
// 
// 0 <= i, j, k, l < n 
// nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
//输出：2
//解释：
//两个元组如下：
//1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1)
// + 2 = 0
//2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1)
// + 0 = 0
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == nums1.length 
// n == nums2.length 
// n == nums3.length 
// n == nums4.length 
// 1 <= n <= 200 
// -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228 
// 
// Related Topics 数组 哈希表 
// 👍 667 👎 0

public class 四数相加II{
	public static void main(String[] args) {
		Solution solution = new 四数相加II().new Solution();
		int [] nums1 = {1,2}, nums2 = {-2,-1}, nums3 = {-1,2}, nums4 = {0,2};
		System.out.println(solution.fourSumCount(nums1, nums2, nums3, nums4));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//	ab	-1 0 1   cd -1 1 2 4
//	     1 2 1       1 1 1 1
	//输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
	//输出：2
	//解释：
	//两个元组如下：
	//1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1)
	// + 2 = 0
	//2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1)
	// + 0 = 0

	/**
	 * 总结，看到形如：A+B....+N=0的式子，
	 * 		要转换为(A+...T)=-((T+1)...+N)再计算，这个T的分割点一般是一半，特殊情况下需要自行判断。
	 * 		定T是解题的关键。
	 */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
	/**
	 * 1.先求 AB数组各个元素求和及 对应的出现次数
	 * 2. 遍历CD之和，判断是否存在 0-CD==AB 若存在，则累计出现次数。
	 * 	 此处类似于两数之和。
	 * 为什么要存 出现次数?:
	 * 	 最后要求 四数之和=0的个数.
	 *   现在已经求出AB的元素和，使用0减去AB ， 若存在AB之和 =0-CD，则 AB出现次数即为 四数之和=0的个数
	 **/
		Map<Integer, Integer> map = new HashMap<>();
		int count = 0;
		for (int i : nums1) {
			for (int j : nums2) {
				int num = i+j;
				if (map.containsKey(num)){
					map.put(num,map.get(num)+1);
				}else {
					map.put(num,1);
				}
			}
		}
		for (int i : nums3) {
			for (int j : nums4) {
				int target = 0 - (i + j);
//				判断 A+B集合中是否存在 0-(C+D)
				if (map.containsKey(target)){
					count += map.get(target);
				}
			}
		}
		return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
